1. Field of the Invention
The present invention relates to an image processing apparatus, method of image data compression and method of image data decompression by which image data can be subjected to fixed length code compression without raster.cndot.block transformation to be stored in the memory, and fixed length coded compressed data corresponding to the image data stored in the memory can be subjected to fixed length decompression without block-raster transformation.
1. Description of the Background Art
As more and more image data come to be digitized, hard copy apparatuses such as printers and copying machines come to be required of various image editing and image processing functions. Conventionally, various methods of data compression have been proposed in order to make compact the volume of image data. At present, JPEG (Joint Photographic Coding Experts Group) method, which is now becoming an international standard, is dominant. The JPEG method is capable of efficiently compressing natural image, and the performance is highly appreciated. This method utilizes the nature that when digital image data is compressed, adjacent image data is, especially in natural images, similar to each other, and in this method, compression is performed block by block, with each block having 8 columns.times.8 rows of pixels.
However, as will be described later, there are functions and characteristics required for the hard copying apparatuses and the like which cannot be sufficiently addressed by the JPEG method. FBTC (Fixed Block Truncation Coding) method, for example, has been proposed as a method of image data compression for such applications.
In the FBTC method, image data is compressed block by block, each block having pixels of 4 columns.times.4 rows. Namely, generally, image data compression is performed on the basis of a block unit having pixels of X columns.times.Y rows, utilizing the nature that adjacent image data are similar to each other.
When image data compression is applied to a hard copy apparatus, for example, at least the following conditions must be satisfied.
1 High image quality can be maintained not dependent on the type of the image.
2 The method is of the type of fixed length coding.
3 High speed processing is possible.
The first condition is derived from the fact that in a hard copy apparatus or the like, high definition images such as computer graphics and character images of which degradation of image quality is much noticed, are often handled, other than the natural images.
The second condition derives from the fact that in order to implement editing function such as magnification, rotation, cut and paste of the images, fixed length coding method which allows easy management of data position even in the compressed state is preferable.
The third condition derives from the fact that real time image compression and decompression is required which corresponds to the high speed processing at the recording portion of the hard copy apparatus or the like.
As will be described in the following, FBTC method is one of the fixed length code image compression and decompression which satisfies the aforementioned conditions. In the FBTC method, the image data is divided into block size of 4.times.4, and compression is performed on the following three components separately.
1 Average level of image data (density value) in the block.
2 Tone width index in the block
3 Quantization level of each pixel
When the compression ratio is 8/3 (the data size after compression is 3/8), the average level and the tone width index of the block have 8 bits, respectively, and quantization level of each image has 2 bits for 16 pixels, that is, a total of 32 bits.
By changing quantization level, input signal system and so on, it is possible to select any of fixed length modes having the compression ratio of 2, 8/3, 4, and 16/3.
Since the FBTC method compresses or decompresses image data based on the above described algorithm, it has the following characteristics.
1 Image quality of not only natural images but also high definition images including computer graphics images and characters is not much degraded.
2 Since it is the fixed length coding method, it allows easy edition of images in the compressed state.
3 Algorithm is simple, allowing implementation in a small scale hardware.
4 High speed processing is possible.
Though the method of image data compression or decompression in accordance with the FBTC method has the above described advantages, it suffers from the following problem when the input image data transmitted serially and successively starting from the first line, such as digital signals obtained from an image sensor such as a CCD (Charge Coupled Device) are to be compressed.
More specifically, the method requires rastereblock transformation for converting the serially transmitted flow of image data to the flow of image data in the unit of a block.
FIG. 46 is a schematic block diagram showing a structure of a conventional image compressing apparatus 1000.
The conventional image compression apparatus 1000 includes a raster.cndot.block transformer 1002 receiving image data input line by line and converting and outputting the received data to data of blocks each having.times.columns.times.Y rows (for example, 4 columns.times.4 rows), a compressor 1004 receiving the data which has been transformed to blocks, performing prescribed image compression on each block and outputting compressed data, and a memory 1006 for storing and holding the compressed data in memory regions allotted to respective blocks.
FIG. 47 illustrates the concept of operation of the image compression apparatus 1000 shown in FIG. 46.
The image data is divided into N columns. Each pixel data is successively input serially line by line in the order of 1, 2, . . . , N-1, N, N+1, . . . , 2N-1, 2N, 2N+1, . . . to raster.cndot.block transformer 1002.
Raster.cndot.block transformer 1002 outputs block data of 4 rows and 4 columns including pixel data of 1, 2, 3, 4, N+1, N+2, . . . , 2N+3, 3N+4 as the first image data block, for the first four rows of image data.
Receiving the first block data, compressor 1004 performs image data compression and outputs the result to memory 1006. In memory 1006, compressed data is stored in the memory region allotted to the data of the first block.
Thereafter, in the similar manner, raster.cndot.block transformer 1002 outputs to compressor 1004 an image data block of 4 columns.times.4 rows including pixels 5, 6, 7, 8, N+5, N+6, . . . , 3N+7, 3N+8 of the first four rows of data. The image data compressed by compressor 1004 is stored in the memory region allotted to the second block, of memory 1006.
Thereafter, in the similar manner, when compression of image data of the first four rows is completed, the data of the next four rows are transformed to blocks, compressed block by block, and stored in memory 1006.
FIG. 46 is a schematic block diagram showing the structure of the raster.cndot.block transformer 1002 shown in FIG. 46.
Raster.cndot.block transformer 1002 includes Y (in the example of FIG. 47, four) FIFO memories (First-In-First-Out Memory) 1200a to 1200d, and a switching circuit 1100 receiving image data transmitted externally line by line, for switching and outputting the data line by line to FIFO memories 1200a to 1200d successively.
More specifically, of the image data transmitted line by line, line of pixel data 1 to N is input to the first FIFO memory 1200a, the line of pixel data N+1 to 2N is input to the second FIFO memory 1200b, the line of pixel data 2N+1 to 3N is input to the third FIFO memory 1200d, and the line of pixel data 3N+1 to 4N is input to the fourth FIFO memory 1200d. Thereafter, from the four FIFO memories 1200a to 1200d, pixel data are output simultaneously on the basis of X pixels, and data in a block unit are output.
When the data compressed block by block are to be decompressed to the original image data, the image data are output block by block. When such image data are to be transmitted to an equipment such as a printer, the data must be transformed to data on line unit basis. Accordingly, in that case, block.cndot.raster transformation is necessary.
FIG. 49 is a schematic block diagram showing a structure of the conventional image decompression apparatus 2000.
Image decompression apparatus 2000 includes a memory 1006 holding the compressed image data, a decompressor 1008 successively reading data held in memory 1006 for performing image data decompression, and a block.cndot.raster transformer 1010 for transforming image data in blocks to data in lines for output.
FIG. 50 is an illustration showing the concept of operation of image decompression apparatus 2000 shown in FIG. 49.
When compressed data of the first block held in memory 1006 is read by decompressor 1008 and decompressed, the image data is transformed to pixel data 1, 2, 3, 4, N+1, N+2, . . . , 3N+3, 3N+4 which correspond to image data of 1 block having 4 columns.times.4 rows, and output to block.raster transformer 1010.
Thereafter, decompressor 1008 decompresses compressed image data of the second block held in memory 1006, transforms the data to pixel data 5, 6, 7, 8, N+5, N+6, . . . , 3N+7, 3N+8 of 1 block, and outputs the pixel data to block.cndot.raster transformer 1010. When decompressor 1008 successively repeats the above described processing and pixel data of the first four lines of the image data are all decompressed, image data are output line by line from block.cndot.raster transformer 1010.
Thereafter, compressed image data of the next four lines held in memory 1006 are decompressed by decompressor 1008, and data of pixel blocks which are the result of image data decompression block by block are output to block.cndot.raster transformer 1010, so that image data of the succeeding four lines are output line by line.
More specifically, from block.cndot.raster transformer 1010, following the data of the first line including pixel data 1, 2, . . . , N-1 and N, the data of the second line including pixel data N+1, . . . , 2N-1 and 2N are output, and in this manner, image data are output line by line.
FIG. 51 is a schematic block diagram showing the structure of the block.cndot.raster transformer shown in FIG. 49.
Referring to FIG. 51, block.cndot.raster transformer 1010 includes Y (in the example shown in FIG. 50, four) FIFO memories 1300a to 1300d receiving image data in the form of blocks output from decompressor 1008, and a switching circuit 1400 for successively switching and outputting line by line the output data from FIFO memories 1300a to 1300d.
More specifically, block.cndot.raster transformer 1010 receives, of the pixel data of respective blocks output from decompressor 1008, the data of the first line at the first FIFO memory 1300a, the data of the second line at the second FIFO memory 1300b, the data of the third line at the third FIFO memory 1300c and the data of the fourth line at the fourth FIFO memory 1300d, and after the end of input of all the blocks of data corresponding to four lines, outputs data successively starting from the first FIFO memory 1300a. Therefore, from block.cndot.raster transformer 1010, the data of the first line including pixel data 1, 2, . . . , N-1 and N are output, thereafter image data of the second line including pixel data N+1, . . . , 2N-1 and 2N are output, and thereafter image data are output line by line successively.
In this manner, the conventional image compression apparatus 1000 includes raster.cndot.block transformer 1002 and compressor 1004, while the image decompression apparatus 2000 includes decompressor 1008 and block.cndot.raster transformer 1010.
However, Y lines of FIFO memories (for an image having the size of VGA, 1 line consists of 640 pixels) are necessary for each of the raster.cndot.block transformer 1002 and block.cndot.raster transformer 1010, which memories are expensive, hindering reduction in cost of image processing apparatuses such as the image compression apparatus and the image decompression apparatus.